package com.tgy.algorithm.base.other;


/**
 * 旋转词
 * abc cab bca
 *
 */
public class _两个字串是否是旋转词 {

    public static boolean isRotaWord(String content,String subStr) {

        if (content == null || content.length() == 0) {
            return false;
        }

        if (subStr == null || subStr.length() == 0) {
            return false;
        }
        int contentLen = content.length();
        int subStrLen = subStr.length();
        if (subStrLen != contentLen) {
            return false;
        }

        String allContent = content + content;
        int index = kmp(allContent, subStr);

        return index != -1;
    }

    public static int[] nexts(String pattern) {

        if (pattern == null || pattern.length() == 0) {
            return new int[]{};
        }

        int len = pattern.length();
        int[] nexts = new int[len];

        nexts[0] = -1;

        int index = 2;
        int preIndex = 0; // 既代表前缀的总数，也代表前缀的下一个值
        char[] chars = pattern.toCharArray();
        while (index < len) {
            if (chars[preIndex] == chars[index - 1]) {
                nexts[index] = preIndex+1;
                preIndex++;
            }else if (preIndex == 0) {
                nexts[index++] = 0;
            }else {
                preIndex = nexts[preIndex];
            }
        }

        return nexts;
    }

    public static int kmp(String content,String pattern) {

        if (content == null || content.length() == 0) {
            return -1;
        }

        if (pattern == null || pattern.length() == 0) {
            return -1;
        }
        int contentLen = content.length();
        int subStrLen = pattern.length();
        if (subStrLen > contentLen) {
            return -1;
        }

        int[] nexts = nexts(pattern);

        int preIndex = 0;
        int index = 0;
        char[] contentChars = content.toCharArray();
        char[] patternChars = pattern.toCharArray();
        while (index < contentLen && preIndex < subStrLen) {
            if (patternChars[preIndex] == contentChars[index]) {
                preIndex++;
                index++;
            }else if (preIndex == 0) {
                index++;
            }else {
                preIndex = nexts[preIndex];
            }
        }

        // 如果preIndex没有走完，则表示pattern串都没有匹配完，直接返回-1
        return preIndex < subStrLen?-1:index - preIndex;
    }

    public static void main(String[] args) {

        String content = "abcdef";
        String pattern = "cdefnb";
        boolean rotaWord = isRotaWord(content, pattern);
        System.out.println(rotaWord);
    }
}
